#include <stdio.h>
#include <stdlib.h>
//顶点的最大个数
#define MAX_VERtEX_NUM 20
//表示顶点之间的关系的变量类型
#define VRType int
//存储弧或者边额外信息的指针变量类型
#define InfoType char
//图中顶点的数据类型
#define VertexType int
//定义bool型常量
typedef enum {false, true} bool;
//设置全局数组，记录标记顶点是否被访问过
bool visited[MAX_VERtEX_NUM];

typedef struct {
    //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值
    VRType adj;
    //弧或边额外含有的信息指针
    InfoType * info;
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    //二维数组，记录顶点之间的关系
    AdjMatrix arcs;
    //存储图中顶点数据
    VertexType vexs[MAX_VERtEX_NUM];
    //记录图的顶点数和弧（边）数
    int vexnum, arcnum;
}MGraph;

typedef struct CSNode {
    VertexType data;
    //孩子结点
    struct CSNode * firstchild;
    //兄弟结点
    struct CSNode * nextsibiling;
}CSNode, * CSTree;

typedef struct Queue {
    //队列中存放的为树结点
    CSTree data;
    struct Queue * next;
}Queue;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for(; i < G.vexnum; i++) {
        if(G.vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if(i > G.vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向图
void CreateDN1(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    G->vexnum = 13;
    G->arcnum = 13;
    //初始化图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        G->vexs[i] = i+1;
    }
    //在二维数组中添加弧的数据
    /*
    {
          1  2  3  4  5  6  7  8  9  10  11  12  13
     1    0  1  1  0  0  1  0  0  0  0   0   0   0
     2    1  0  0  0  0  0  0  0  0  0   0   0   1
     3    1  0  0  0  0  0  0  0  0  0   0   0   0
     4    0  0  0  0  1  0  0  0  0  0   0   0   0
     5    0  0  0  1  0  0  0  0  0  0   0   0   0
     6    1  0  0  0  0  0  0  0  0  0   0   0   0
     7    0  0  0  0  0  0  0  1  1  1   0   0   0
     8    0  0  0  0  0  0  1  0  0  1   0   0   0
     9    0  0  0  0  0  0  1  0  0  0   0   0   0
    10    0  0  0  0  0  0  1  1  0  0   0   0   0
    11    0  0  0  0  0  0  0  0  0  0   0   1   1
    12    1  0  0  0  0  0  0  0  0  0   1   0   1
    13    0  1  0  0  0  0  0  0  0  0   1   1   0
    }
    */
   for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
   }
   //无向图的二阶矩阵沿主对角线对称
   //V1-V2
   G->arcs[0][1].adj = 1;
   G->arcs[1][0].adj = 1;
   //V1-V3
   G->arcs[0][2].adj = 1;
   G->arcs[2][0].adj = 1;
   //V1-V6
   G->arcs[0][5].adj = 1;
   G->arcs[5][0].adj = 1;
   //V1-V12
   G->arcs[0][11].adj = 1;
   G->arcs[11][0].adj = 1;
   //V2-V13
   G->arcs[1][12].adj = 1;
   G->arcs[12][1].adj = 1;
   //V4-V5
   G->arcs[3][4].adj = 1;
   G->arcs[4][3].adj = 1;
   //V7-V8
   G->arcs[6][7].adj = 1;
   G->arcs[7][6].adj = 1;
   //V7-V9
   G->arcs[6][8].adj = 1;
   G->arcs[8][6].adj = 1;
   //V7-V10
   G->arcs[6][9].adj = 1;
   G->arcs[9][6].adj = 1;
   //V8-V10
   G->arcs[7][9].adj = 1;
   G->arcs[9][7].adj = 1;
   //V11-V12
   G->arcs[10][11].adj = 1;
   G->arcs[11][10].adj = 1;
   //V11-V13
   G->arcs[10][12].adj = 1;
   G->arcs[12][10].adj = 1;
   //V12-V13
   G->arcs[11][12].adj = 1;
   G->arcs[12][11].adj = 1;
}

void CreateDN(MGraph * G) {
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //输入图含有的顶点数据
    for(int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    //初始化图
    for(int i = 0; i < G->vexnum; i++) {
        for(int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
    }
    //查找元素位置，记录弧
    for(int i = 0 ; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d",&v1,&v2);
        int n = LocateVex(*G, v1);
        int m = LocateVex(*G, v2);
        if(m == -1 || n == -1) {
            printf("not found\n");
            return;
        }
        //无向图的二阶矩阵沿主对角线对称
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
}

int FirstAdjVex(MGraph G, int v) {
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

int NextAdjVex(MGraph G, int v, int w) {
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for(int i = w+1; i < G.vexnum; i++) {
        if(G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}
//初始化队列
void InitQueue(Queue ** Q) {
    (*Q) = (Queue *)malloc(sizeof(Queue));
    (*Q)->next = NULL;
}
//结点v进队列
void EnQueue(Queue ** Q, CSTree T) {
    Queue * element = (Queue *)malloc(sizeof(Queue));
    element->data = T;
    element->next = NULL;
    
    Queue * temp = (*Q);
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = element;
}
//队头元素出队列
void DeQueue(Queue ** Q, CSTree * T) {
    (*T) = (*Q)->next->data;
    (*Q)->next = (*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Queue * Q) {
    if(Q->next == NULL) {
        return true;
    }
    return false;
}
void BFSTree(MGraph G, int v, CSTree * T){
    CSTree t = NULL;
    Queue * q;
    InitQueue(&q);
    //根结点入队
    EnQueue(&q, (*T));
    //当队列为空时，证明遍历完成
    while (!QueueEmpty(q))
    {
        /* code */
        bool first = true;
        //队列首个结点出队
        DeQueue(&q, &t);
        //判断结点中的数据在数组中的具体位置
        int v = LocateVex(G, t->data);
        //已经访问过的更改其标志位
        visited[v] = true;
        //遍历以出队结点为起始点的所有邻接点
        for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
            //标志位为false，证明未遍历过
            if(!visited[w]) {
                //新建一个结点 p，存放当前遍历的顶点
                CSTree p = (CSTree)malloc(sizeof(CSTree));
                p->data = G.vexs[w];
                p->firstchild = NULL;
                p->nextsibiling = NULL;
                //当前结点入队
                EnQueue(&q, p);
                //更改标志位
                visited[w] = true;
                //如果是出队顶点的第一个邻接点，设置p结点为其左孩子
                if(first) {
                    t->firstchild = p;
                    first = false;
                } else {
                    t->nextsibiling = p;
                }
                t = p;
            }
        }
    }
}
//广度优先搜索生成森林并转化为二叉树
void BFSForest(MGraph G, CSTree * T) {
    (*T) = NULL;
    //每个顶点的标记为初始化为false
    for(int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    CSTree t = NULL;
    //遍历图中所有的顶点
    for(int v = 0; v < G.vexnum; v++) {
        //如果该顶点的标记位为false，证明未访问过
        if(!visited[v]) {
            //新建一个结点，表示该顶点
            CSTree p = (CSTree)malloc(sizeof(CSTree));
            p->data = G.vexs[v];
            p->firstchild = NULL;
            p->nextsibiling = NULL;
            //如果树为空，则该顶点作为树的树根
            if(!(*T)) {
                (*T) = p;
            } else {
                //该顶点作为树根的兄弟结点
                t->nextsibiling = p;
            }
            //每次都要把t指针指向新的结点，为下次添加结点做铺垫
            t = p;
            //以该结点为起始点，构建广度优先生成树
            BFSTree(G, v, &p);
        }
    }
}

void PrintGraph(MGraph G) {
    for(int i = 0 ; i < G.vexnum; i++) {
        for(int j = 0; j < G.vexnum; j++) {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}
//前序遍历二叉树
void PreOrderTraverse(CSTree T) {
    if(T) {
        printf("%d ", T->data);
        PreOrderTraverse(T->firstchild);
        PreOrderTraverse(T->nextsibiling);
    }
    return;
}

int main(int argc, char * argv[]) {
    //建立一个图的变量
    MGraph G;
    //调用创建函数，传入地址参数
    CreateDN1(&G);
    //调用创建函数，传入地址参数
    //CreateGraph(&G);
    //输出图的二阶矩阵
    PrintGraph(G);
    printf("\n");
    CSTree T;
    //深度优先搜索森林
    BFSForest(G, &T);
    PreOrderTraverse(T);
    return 0;
}
